package com.dragon.datastructure.tree.binarysearchtree;

import java.util.ArrayDeque;

/**
 * 二分搜索树
 *
 * @author dragon
 * @since 2019/12/30
 */
public class BinarySearchTree<E extends Comparable<E>> {

    public int size() {

        return size;
    }

    private static class Node<E> {
        E item;
        Node<E> left;
        Node<E> right;

        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }

        public Node() {
        }
    }

    private Node<E> root;

    private int size;

    /**
     * 元素个数是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素
     *
     * @param e
     */
    public void add(E e) {
        root = addRec(root, e);
    }

    private Node<E> addRec(Node<E> root, E e) {
        if (root == null) {
            size++;
            return new Node<>(e, null, null);
        }
        if (root.item.compareTo(e) > 0) {
            root.left = addRec(root.left, e);
            return root;
        } else if (root.item.compareTo(e) < 0) {
            root.right = addRec(root.right, e);
            return root;
        } else {
            return root;
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        midOrderRec(root, 0);
    }

    private void midOrderRec(Node<E> root, Integer count) {
        if (root == null) {
            return;
        }
        midOrderRec(root.left, count);
        System.out.print(root.item + " 名次:" + ++count);
        midOrderRec(root.right, count);
    }


    /**
     * 前序遍历的非递归写法
     */
    public void preOrderNC() {
        if (root == null) {
            return;
        }
        ArrayDeque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            System.out.print(pop.item + " ");
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }

    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        ArrayDeque<Node<E>> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            Node<E> cur = deque.poll();
            System.out.print(cur.item + " ");
            if (cur.left != null) {
                deque.offer(cur.left);
            }

            if (cur.right != null) {
                deque.offer(cur.right);
            }
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrderRecur(root);
    }


    private void preOrderRecur(Node<E> root) {
        if (root == null) {
            return;
        }
        System.out.print(root.item + " ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        afterOrderRecur(root);
    }

    private void afterOrderRecur(Node<E> root) {
        if (root == null) {
            return;
        }
        afterOrderRecur(root.left);
        afterOrderRecur(root.right);
        System.out.print(root.item + " ");
    }

    /**
     * 查询二分搜索树中的最小值
     *
     * @return
     */
    public E minimum() {
        if (isEmpty()) {
            throw new RuntimeException("没有元素");
        }

        return minimum(root).item;
    }

    private Node<E> minimum(Node<E> root) {
        if (root.left == null) {
            return root;
        }

        return minimum(root.left);
    }

    /**
     * 删除二分搜索树中最小的元素
     *
     * @return
     */
    public E removeMin() {
        if (isEmpty()) {
            throw new RuntimeException("二分搜素树为空");
        }
        E ret = minimum();
        root = removeMin(root);

        return ret;
    }

    private Node<E> removeMin(Node<E> root) {
        if (root.left == null) {
            Node rightNode = root.right;
            root.right = null;
            size--;
            return rightNode;
        }

        root.left = removeMin(root.left);

        return root;
    }

    /**
     * 删除二分搜素树中最大的元素
     *
     * @return
     */
    public E removeMax() {
        if (isEmpty()) {
            throw new RuntimeException("没有元素");
        }
        E ret = maximum();

        root = removeMax(root);

        return ret;
    }

    private Node<E> removeMax(Node<E> root) {
        if (root.right == null) {
            Node leftNode = root.left;
            root.left = null;
            size--;
            return leftNode;
        }

        root.right = removeMax(root.right);

        return root;
    }

    /**
     * 查询二分搜索树中的最大值
     *
     * @return
     */
    public E maximum() {
        if (isEmpty()) {
            throw new RuntimeException("没有元素");
        }

        return maximum(root).item;
    }

    private Node<E> maximum(Node<E> root) {
        if (root.right == null) {
            return root;
        }


        return maximum(root.right);
    }


    /**
     * 如果二分搜索树中有元素与e相等，则返回该元素
     * 不然的话，就返回小于e并且是最大的那个元素(小于e最接近e的那个元素)
     * <p>
     * 思路分析: 如果node 比 e 大， 则 要找到的节点 一定在 node 左子树中
     * <p>
     * 如果node 比 e 小的话， node 的左子树就可以直接排除了，因为 node 的左子树都比 node 小
     * a. 要么就是node
     * b. 要么node的右子树中还有比 e 小 但是 比 node 大的 元素
     *
     * @param e
     * @return
     */
    public E floor(E e) {
        if (isEmpty() || minimum().compareTo(e) > 0) {
            return null;
        }

        Node<E> ret = floor(root, e);

        return ret.item;
    }

    private Node<E> floor(Node<E> root, E e) {
        if (root == null) {
            return null;
        }

        if (root.item.compareTo(e) == 0) {
            return root;
        }

        if (root.item.compareTo(e) > 0) {
            return floor(root.left, e);
        }

        Node<E> tmpNode = floor(root.right, e);
        if (tmpNode != null) {
            return tmpNode;
        }

        return root;
    }

    /**
     * 如果二分搜索树中的元素等于 e ，则返回该元素
     * <p>
     * 不然 找到比 e 大的最小的元素
     * <p>
     * 如果 node.item < e ,则想要找到的元素则一定在 node的右子树
     * <p>
     * 否则，1.要么就是返回该节点， 要么 就是 在该node节点的左子树中查找，如果找到，返回，如果找不到则返回node
     *
     * @param e
     * @return
     */
    public E ceil(E e) {
        if (isEmpty() || maximum().compareTo(e) < 0) {
            return null;
        }

        return ceil(root, e).item;
    }

    private Node<E> ceil(Node<E> root, E e) {
        if (root == null) {
            return null;
        }
        if (root.item.compareTo(e) == 0) {
            return root;
        }

        if (root.item.compareTo(e) < 0) {
            return ceil(root.left, e);
        }

        Node<E> tmpNode = ceil(root.left, e);
        if (tmpNode != null) {
            return tmpNode;
        }

        return root;
    }

    /**
     * 从二分搜索树中删除元素为e的节点
     *
     * @param e 待删除的元素
     */
    public void remove(E e) {
        root = removeRec(root, e);
    }

    private Node<E> removeRec(Node<E> root, E e) {
        if (root == null) {
            return null;
        }

        if (root.item.compareTo(e) > 0) {
            root.left = removeRec(root.left, e);

            return root;
        } else if (root.item.compareTo(e) < 0) {
            root.right = removeRec(root.right, e);

            return root;
        } else { // root.item.compareTo(e) == 0
            if (root.left == null) {
                Node<E> rightNode = root.right;
                root.right = null;
                size--;
                return rightNode;
            }

            if (root.right == null) {
                Node<E> leftNode = root.left;
                root.left = null;
                size--;
                return leftNode;
            }

            // 找到待删除的节点的右子树中的最小值，该节点将会替代被删除的节点
            Node<E> successor = minimum(root.right);
            successor.right = removeMin(root.right);
            successor.left = root.left;

            root.left = root.right = null;

            return successor;
        }
    }

    /**
     * 判断二分搜索树是否包含 e 这个元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {

        return containsRec(root, e);
    }

    private boolean containsRec(Node<E> root, E e) {
        if (root == null) {
            return false;
        }
        if (root.item.equals(e)) {
            return true;
        } else if (root.item.compareTo(e) > 0) {
            return containsRec(root.left, e);
        } else {
            return containsRec(root.right, e);
        }
    }


}
